package hash;

import java.util.HashMap;
import java.util.Map;
import java.util.NoSuchElementException;

/**
 * 基于开散列（哈希桶）方案下的哈希表的实现
 */
public class MyHashMap {
    /**
     * 哈希表中存储的元素
     */
    private class Node {
        private int key; // 以此值作为哈希表的查找字段
        private int val;
        private Node next;

        Node (int key, int val) {
            this.key = key;
            this.val = val;
        }

        Node (int key, int val, Node next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }

    private int size; // 哈希表中实际存储元素数量
    private static final int DEFAULT_CAPACITY = 16; // 设置哈希表的默认长度为16
    private static final double LOAD_FACTOR = 0.75; // 默认负载因子为0.75
    private int M; // 取模数
    private Node[] data; // 存储数据的Node类型数组

    public MyHashMap() {
        // 使用有参数的构造方法
        this(DEFAULT_CAPACITY);
    }

    public MyHashMap(int capacity) {
        data = new Node[capacity];
        M = capacity; // 设置取模数为数组长度
    }

    /**
     * 哈希函数，获取键值key的哈希地址（索引）
     * @param key
     * @return
     */
    public int hash(int key) {
        return Math.abs(key) % M;
    }

    /**
     * 向哈希表中添加键值为key的元素
     * @param key
     * @param val
     * @return 返回val值
     */
    public int add(int key, int val) {
        // 取得索引
        int index = hash(key);
        // 遍历哈希表，看是否已存在该元素，若存在就修改对应的val
        for (Node node = data[index]; node != null; node = node.next) {
            if (node.key == key) {
                node.val = val;
                return val;
            }
        }
        // 至此说明该索引位置不存在key对应的元素，进行头插
        Node node = new Node(key, val, data[index]);
        data[index] = node;
        size ++;
        // 添加完成后判断是否data需要扩容
        if (size / LOAD_FACTOR >= M) {
            // 需要扩容，数组长度扩至原来的一倍
            reSize();
        }
        return val;
    }

    /**
     * 删除哈希表中指定键值为key的元素
     * @param key
     * @return 返回键值key对应的val
     */
    public int remove(int key) {
        // 获取索引
        int index = hash(key);
        // 判断头结点是否是待删除节点
        // 如果是头节点需要对data数组中存储的元素修改
        Node head = data[index];
        if (head != null && head.key == key) {
            data[index] = head.next;
            int val = head.val;
            head = head.next = null;
            size --;
            return val;
        }
        // 至此，说明index处的头结点不是待删除节点
        // 仅仅只需要对头结点之后链上的元素修改
        Node prev = head;
        while (prev != null && prev.next != null) {
            Node cur = prev.next;
            if (cur.key == key) {
                prev.next = cur.next;
                int val = cur.val;
                cur = cur.next = null;
                size --;
                return val;
            }
            prev = prev.next;
        }
        // 至此，说明没有查找到该元素
        throw new NoSuchElementException("The element does‘t exist in the hash！Remove error!");
    }

    /**
     * 判断哈希表中是否存在键值为key的元素
     * @param key
     * @return
     */
    public boolean containsKey(int key) {
        int index = hash(key);
        for (Node node = data[index]; node != null; node = node.next) {
            if (node.key == key) {
                return true;
            }
        }
        return false;
    }

    /**
     * 判断哈希表中是否存在元素值为val
     * @param val
     * @return
     */
    public boolean containsValue(int val) {
        // 遍历整个哈希表
        for (int i = 0; i < data.length; i++) {
            if (data[i] != null) {
                for (Node node = data[i]; node != null; node = node.next) {
                    if (node.val == val) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    /**
     * 对data进行扩容
     */
    private void reSize() {
        Node[] newData = new Node[data.length << 1];
        M = newData.length;
        for (int i = 0; i < data.length; i++) {
            if (data[i] != null) {
                for (Node node = data[i]; node != null;) {
                    Node next = node.next;
                    int index = hash(node.key);
                    node.next = newData[index];
                    newData[index] = node;
                    node = next;
                }
            }
        }
        data = newData;
    }
}

class Test {
    public static void main(String[] args) {
        MyHashMap myHashMap = new MyHashMap(8);
        myHashMap.add(10, 3);
        myHashMap.add(7, 8);
        myHashMap.add(2, 1);
//        System.out.println("哈希表中是否存在键值为1的元素：" + myHashMap.containsKey(1));
//        System.out.println("哈希表中是否存在键值为7的元素：" + myHashMap.containsKey(7));
//        System.out.println("哈希表中是否存在值为3的元素：" + myHashMap.containsValue(3));
//        System.out.println("哈希表中是否存在值为7的元素：" + myHashMap.containsValue(7));
//        myHashMap.remove(10);
        // 扩容
        myHashMap.add(17, 8);
        myHashMap.add(1, 6);
        myHashMap.add(18, 3);
        System.out.println();
    }
}
